The present invention relates to digital data transmission and, in particular, to error correcting codes.
Continued advances in forward error-correcting codes, such as convolutional codes and trellis codes, have enabled designers of modems, wireless communications systems and other digital communications systems to achieve increased bit rates for a given level of error rate performance. Among the various innovations that have been introduced over the years are so-called turbo codes. At the heart of the turbo code concept is the encoding of input data using more than one encoder combined with an interleaver in such a way that improved performance (as compared to a single encoding) can be achieved using a corresponding number of so-called soft input/soft output decoders which operate iteratively.
An early description of turbo codes appears in C. Berrou, et al, xe2x80x9cNear Shannon limit error-correcting coding and decoding: Turbo codes,xe2x80x9d Proc. 1993 Int. Conf. Communication (Geneva, Switzerland, May 1993), pp. 1064-1070. Berrou et al discloses a so-called parallel-concatenated turbo code. The input data is applied to a first convolutional encoder and an interleaved version of the input data is applied to a second convolutional encoder. The output bits of the two encoders are then mapped into signal points of a two-dimensional (2D) 4-PSK signaling constellation for transmission. Some of the redundant bits generated by the encoders may be subjected to a so-called puncturing prior to the mapping step in order to improve bandwidth efficiency (measured in bits per 2D signal point).
At relatively high error rates, a parallel concatenated turbo code provides excellent coding gain, thereby advantageously reducing the level of received signal-to-noise ratio required in order to realize a desired level of error rate performance. Disadvantageously, however, achieving that excellent coding gain requires an extremely long interleaver. This introduces significant end-to-end delay, or latency, which is undesirable in many applications. Moreover, a parallel-concatenated turbo code exhibits a so-called error floor phenomenon wherein the improvement in coding gain is far less dramatic at lower error rates and, indeed, may be comparable to, or even worse than, that achieved using more conventional encoding and decoding.
Also known in the prior art are so-called serial-concatenated turbo codes, as disclosed, for example, by S. Benedetto, et al, xe2x80x9cSerial concatenation of interleaved codes: Performance analysis, design, and iterative decoding,xe2x80x9d IEEE Trans. Inform. Theory, vol. 44, pp. 909-926, May 1998. Here, the input data is applied to a first convolutional encoder and the output bits of the first encoder, after interleaving, are used as the input bits for a second convolutional encoder. The output bits of the second encoder are then mapped into signal points of a 2D 4-PSK signaling constellation for transmission. The above-mentioned error floor phenomenon is less pronounced for serial-concatenated turbo codes than for parallel-concatenated turbo codes, thereby providing better coding gain at lower error rates. However, these serial-concatenated turbo codes generate more redundant bits than in the parallel case, so that they are less bandwidth-efficient. Moreover, they too require a long interleaver.
Neither the parallel-concatenated, nor the serial-concatenated turbo codes described in the above-discussed prior art references are bandwidth efficient; each of them has a bandwidth efficiency of less than two bits per 2D signal point. More bandwidth-efficient parallel concatenated turbo codes are known, however. See, for example, S. Benedetto, et al, xe2x80x9cBandwidth efficient parallel concatenated coding schemes,xe2x80x9d Electron. Lett., vol. 31, pp. 2067-2069, 1995, and P. Robertson, et al, xe2x80x9cCoded modulation scheme employing turbo codes,xe2x80x9d Electron. Lett., vol. 31, pp. 1546-1547, 1995. The arrangements disclosed in these references achieve high coding gains at high error rate while featuring an improved bandwidth efficiency of a full 2 bits per 2D signal point by using rate-2/3 trellis codes designed jointly with a 2D 8-PSK signaling constellation rather than the convolutional codes with a 2D 4-PSK constellation used in the Berrou arrangement. However, these latter codes still exhibit the above-mentioned error floor phenomenon and long delays.
The prior art also teaches that another way of achieving increased bandwidth efficiency while achieving the advantages of the turbo code approach is to employ so-called multi-level coding in which the code used in at least one of the levels is a parallel-concatenated turbo code of the kind disclosed by Berrou. (As is well known, a multilevel code is one in which the output bits of different codes are used to select increasingly finer subsets, and ultimately a single signal point, of the signal constellation.) Such a code is disclosed in U. Wachsmann, et al, xe2x80x9cPower and bandwidth efficient digital communication using turbo codes in multilevel codes,xe2x80x9d Euro. Trans. Telecommun., vol. 6, pp. 557-567, September 1995. However, the error floor and delay characteristics of such a multi-level code promise to be no betterxe2x80x94and may prove to be worsexe2x80x94than that of the parallel-concatenated turbo code used in a non-multi-level-coding arrangement.
U.S. application Ser. No. 09/451070, filed Nov. 30, 1999, entitled Serial-concatenated Turbo Codes, is directed to serial-concatenated turbo codes, which were defined therein to mean turbo codes for which at least some of the output bits, including at least one redundant bit, provided by a first, outer encoder are further processed, after interleaving, by a second, inner encoder. Such turbo codes may be of any desired dimensionality, Nxe2x89xa71, meaning that the data to be transmitted is represented by an N-tuple, or N-dimensional symbol, whose N coordinates are selected by the output bits of the encoders interdependently. For example, when N is an even integer, an N-dimensional symbol may be conveniently transmitted, during an N-dimensional xe2x80x9csymbol interval,xe2x80x9d as a combination of N/2 2D signal points, wherein each so-called signal space coordinate of the 2D signal point is represented, during a 2D xe2x80x9csignaling interval,xe2x80x9d by the amplitude of an in-phase or quadrature-phase component of a modulated carrier signal. Thus the aforementioned symbol interval is made up of N/2 signaling intervals. For the code where N=2, the symbol interval and the signaling interval are the same.
More specifically, in turbo codes embodying the principles of the invention of U.S. application Ser. No. 09/451070, a) the state of each of the inner and outer encoders is advanced only once per symbol interval, and b) all of the data bits, and at least one redundant bit generated by one or both of the encoders for that symbol interval are transmitted together during a single symbol interval, and c) the inner and outer encoders are trellis encoders. This approach advantageously provides turbo codes having a lower delay than prior arrangements and, in addition, affords an advantageous combination of error rate performance, bandwidth efficiency, and decoder complexity not achieved by prior arrangements and exhibiting a less pronounced (or perhaps no) error floor. The inner and outer codes may be of any desired dimensionality.
Arrangements embodying the principles of the invention of U.S. application Ser. No. 09/451070 utilize a signal constellation of sufficient size (i.e., number of symbols in the constellation) to accommodate the transmission of the data bits and redundant bits within the aforementioned single symbol interval. Moreover, in preferred embodiments, the turbo code, the constellation, and the mapping between the bits to be transmitted and the constellation symbols are selected in view of one another in such a way that the code complexity and interleaving delay necessary to achieve a given level of error rate performance are less than they would be if the turbo code, constellation and mapping were not selected in view of one another. This is referred to in the art as a xe2x80x9cjoint design,xe2x80x9d as more formally defined hereinbelow.
With respect to the interleaver, the prior art serial turbo codes have employed bit interleavers between the first and second convolutional encoders. The bit interleaver interleaves the output of the first convolutional encoder on a bit-by-bit basis and provides the interleaved bits to the second convolutional encoder. The output bits of the second encoder are then mapped into signal points as described above.
One of the problems with bit interleaving between the first and second convolutional encoders as known in the art is that a bit interleaver typically uses a large so-called interleaving frame, and hence imposes a significant interleaving and deinterleaving delay.
In accordance with the invention, a symbol interleaver which interleaves output bits of a first redundancy encoder and provides interleaved bits to a second redundancy encoder, uses as its interleaved elements the bits associated with a particular symbol interval, rather than, for example, individual bits, or the bits associated with the constituent signaling intervals of the symbol interval. Thus, the symbol interleaver interleaves all bits associated with a particular symbol interval on a bit-group-by-bit-group level. I have found that such an approach advantageously drastically reduces the delay introduced by the interleaver and simplifies the steps required to terminate the turbo code.
In accordance with one embodiment of the invention, a predetermined number of input bits associated with a particular symbol interval are encoded using a first redundancy code to generate first redundancy encoded output bits. These first redundancy encoded output bits, along with any other remaining input bits associated with the particular symbol interval which were not encoded using the first redundancy code, are interleaved as a group by the interleaver. A predetermined number of bits of an interleaved group of bits are encoded using a second redundancy code to generate second redundancy encoded output bits. These second redundancy encoded output bits, along with any other remaining bits of the interleaved group of bits associated with the particular symbol interval which were not encoded using the second redundancy code, are then used to generate a data symbol. Thus, in accordance with the principles of the invention, all bits associated with a particular symbol interval (and which are used to generate a particular data symbol) are interleaved as a group. In the above described embodiment, any remaining input bits associated with the particular symbol interval which were not encoded using the first redundancy code, were part of the interleaved group of bits. However, these data bits that are not encoded by the first redundancy code do not need to be interleaved along with the output bits of the first redundancy code.
In advantageous embodiments of the invention, the interleaver stores n=Jxc3x97K groups of bits as an interleaving frame in a Jxc3x97K matrix. Values for J and K are chosen so as to match the interleaving to a particular turbo code. In particular, J is selected as a function of the so-called decoding depth of the second redundancy code and K is selected as a function of the decoding depth of the first redundancy code.
In further advantageous embodiments, the bit groups are inserted into each row of the matrix in accordance with a pattern in which successive input bit groups are separated by K1 columns. In addition, the bit groups are inserted into each column of the matrix in accordance with a pattern in which successive contiguous K input bit groups are separated either by J1 or (J1xe2x88x921) rows (when J1=J/2). The bit groups are thereafter read out of the interleaver matrix on a column-by-column basis. The overall effect is that any two successive bit groups at the input of the interleaver will be separated by at least K1xc3x97J bit groups at the output of the interleaver and any two successive bit groups at the output of the interleaver separated by at least (J/J1xc3x97K) bit groups at the input of the interleaver.
These and other advantages of the invention will be apparent to those of ordinary skill in the art by reference to the following detailed description and the accompanying drawings.